package 算法;

import java.security.Principal;

public class BasicSearchDemo3 {
    public static void main(String[] args) {
/*
分块查找
核心思想：
块内无序，块间有序
实现步骤：
1.创建数组blockArr存放每一个块对象的信息
2.先查找blockArr确定要查找的数据属于哪一块
3.再单独遍历这一块数据即可
*/
        int[] arr = {16, 5, 9, 12, 21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};
        //创建三个块对象
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(73, 12, 17);
        //放入数组中管理
        Block[] blockArr = {b1, b2, b3};
        //要查找的数
        int number = 37;
        //写方法查找
        int indext = getIndext(blockArr, arr, number);
        System.out.println(indext);
    }

    //找索引
    public static int getIndext(Block[] blockArr, int[] arr, int number) {
        int k = findBlock(blockArr, number);
        if (k == -1) {
            System.out.println("number不在数组中");
            return -1;
        } else {
            for (int i = blockArr[k].getStarindext(); i <= blockArr[k].getEndindext(); i++) {
                if(number==arr[i])
                {
                    return i;
                }
            }
        }
        return -1;
    }
    //查找块
    public static int  findBlock(Block []blockArr,int number){
        for(int i=0;i<blockArr.length;i++)
        {
            if(number<=blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}
class Block {
    private int max;
    private int starindext;
    private int endindext;

    public Block() {
    }

    public Block(int max, int starindext, int endindext) {
        this.max = max;
        this.starindext = starindext;
        this.endindext = endindext;
    }

    /**
     * 获取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     * @return starindext
     */
    public int getStarindext() {
        return starindext;
    }

    /**
     * 设置
     * @param starindext
     */
    public void setStarindext(int starindext) {
        this.starindext = starindext;
    }

    /**
     * 获取
     * @return endindext
     */
    public int getEndindext() {
        return endindext;
    }

    /**
     * 设置
     * @param endindext
     */
    public void setEndindext(int endindext) {
        this.endindext = endindext;
    }

    public String toString() {
        return "Block{max = " + max + ", starindext = " + starindext + ", endindext = " + endindext + "}";
    }
}
